package com.xzz.sort;

import java.util.*;

/**
 * @author: hhz
 * @create: 2021-12-14 15:53
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *
 * 进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
 **/
public class TopK {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,2,2,2,3,4,5,5,5,5};
        int[] arr = topKFrequent(nums, 2);
        System.out.println(Arrays.toString(arr));
    }
    public static int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            map.put(num,map.getOrDefault(num,0)+1);
        }
        List<Node> arr = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            arr.add(new Node(entry.getKey(),entry.getValue()));
        }
        int length = arr.size();
        for(int i = arr.size()/2-1;i>=0;i--){
            minHeap(arr,i,length);
        }
        minHeapSort(arr);
        int[] res = new int[k];
        for(int i=0;i<k;i++){
            res[i]=arr.get(i).key;
        }
        return res;
    }
    static class Node implements Comparable<Node>{
        int key;
        int value;
        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }


        @Override
        public int compareTo(Node o) {
            return this.value-o.value;
        }
    }
    //构建小顶堆
    public static void minHeap(List<Node> arr,int i,int length){
        int max = i ;
        int left = 2*i+1;
        int right = 2*i+2;
        if(left<length && arr.get(left).compareTo(arr.get(max))<0){
            max = left;
        }
        if(right<length && arr.get(right).compareTo(arr.get(max))<0){
            max = right;
        }
        if(max!=i){
            swap(arr,max,i);
            minHeap(arr,max,length);
        }
    }
    public static void swap(List<Node> arr,int i,int j){
        Node temp = arr.get(i);
        arr.set(i,arr.get(j));
        arr.set(j,temp);
    }
    //利用小顶堆降序排序
    public static void minHeapSort(List<Node> arr){
        int length = arr.size();
        for (int i = arr.size() - 1; i >= 0; i--) {
            //根节点(第一个节点)与最后一个叶子节点交换
            swap(arr,0,i);
            //交换后剩下的节点从根节点处重新构建小顶堆
            minHeap(arr,0,--length);
        }
    }
}
